#include <iostream>
#include <algorithm>
#include <string>

int k, len;
std::string s;

bool judge(int l)
{
	std::string str = s;
	int t = 0;
	for (int i = 0; i < len; i++) {
		if (str[i] == '1') {
			for (int j = i; j < std::min(i + l, len); j++) str[j] = '0';
			t++;
		}
	}
	return (t <= k);
}

int main()
{
	int T;
	std::cin >> T;
	while (T--) {
		std::cin >> len >> k;
		std::cin >> s;

		int l = 0, r = len;
		while (l + 1 <= r) {
			int mid = (l + r)/2;
			if (judge(mid)) r = mid;
			else            l = mid + 1;
		}
		if (judge(l)) r = l;
		std::cout << r << '\n';
	}
}

